package airthmetic.exercise.search;

import java.util.*;

public class _127_单词接龙 {
    // 单向方式
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<String>(wordList);
        if(!set.contains(endWord)){
            return 0;
        }

        Queue<String> queue = new LinkedList();
        Set<String> visited = new HashSet();
        int step = 1;

        queue.offer(beginWord);
        visited.add(beginWord);

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                String word = queue.poll();

                boolean b = canConvert(word, endWord, set, visited, queue);
                if(b){
                    return step + 1;
                }
            }
            step++;
        }
        return 0;
    }

    public boolean canConvert(String word, String endWord, Set<String> set, Set<String> visited, Queue<String> queue){
        char[] charArray = word.toCharArray();
        for(int i=0; i<charArray.length; i++){
            char origin = charArray[i];

            for(char c = 'a'; c<='z'; c++){
                if(charArray[i] == c){
                    continue;
                }
                charArray[i] = c;
                String newWord = new String(charArray);

                if(endWord.equals(newWord)){
                    return true;
                }

                if(set.contains(newWord) && !visited.contains(newWord)){
                    queue.offer(newWord);
                    visited.add(newWord);
                }
            }
            charArray[i] = origin;
        }
        return false;

    }


    // 双向BFS
    public int ladderLength2(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<String>(wordList);
        if(!set.contains(endWord)){
            return 0;
        }
        Queue<String> q1 = new LinkedList();
        Set<String> v1 = new HashSet();
        Queue<String> q2 = new LinkedList();
        Set<String> v2 = new HashSet();

        q1.offer(beginWord);
        v1.add(beginWord);
        q2.offer(endWord);
        v2.add(endWord);

        int step = 1;



        while(!q1.isEmpty() && !q2.isEmpty()){
            // 转换一下 保证每次从顶点更少的一端出发
            if(q1.size() > q2.size()){
                // 转换
                Queue<String> temp;
                temp = q1;
                q1 = q2;
                q2 = temp;

                Set<String> tem;
                tem = v1;
                v1 = v2;
                v2 = tem;
            }
            int size = q1.size();
            for(int i=0; i<size; i++){
                String word = q1.poll();
                char[] charArray = word.toCharArray();
                for(int j=0; j<charArray.length; j++){
                    char origin = charArray[j];
                    for(char c = 'a'; c<='z'; c++){
                        if(c == origin){
                            continue;
                        }
                        charArray[j] = c;
                        String newWord = new String(charArray);
                        if(v1.contains(newWord)){
                            continue;
                        }
                        if(v2.contains(newWord)){
                            return step + 1;
                        }
                        if(set.contains(newWord)){
                            q1.offer(newWord);
                            v1.add(newWord);
                        }
                    }
                    charArray[j] = origin;
                }
            }
            step++;
        }
        return 0;
    }
}
